We present a simple but powerful reinterpretation of kernelizedlocality-sensitive hashing (KLSH), a general and popular method developed inthe vision community for performing approximate nearest-neighbor searches in anarbitrary reproducing kernel Hilbert space (RKHS). Our new perspective is basedon viewing the steps of the KLSH algorithm in an appropriately projected space,and has several key theoretical and practical benefits. First, it eliminatesthe problematic conceptual difficulties that are present in the existingmotivation of KLSH. Second, it yields the first formal retrieval performancebounds for KLSH. Third, our analysis reveals two techniques for boosting theempirical performance of KLSH. We evaluate these extensions on severallarge-scale benchmark image retrieval data sets, and show that our analysisleads to improved recall performance of at least 12%, and sometimes muchhigher, over the standard KLSH method.
展开▼
